package org.datastructure.firstday.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 10, 6, 9, 1, 4};

        qSort1(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    public static void qSort1(int[] arr, int left, int right) {


        int l = left, r = right, temp;

        if (l < r) {
            // TODO: 必须先判断l<r后，才能赋值给temp，如果当l=r，迭代的时候会将r+1和r-1，此时
            temp = arr[l];
            while (l < r) {

                // TODO: 基数选择第一个元素《必须要先从r开始右移动》1.解释，https://blog.csdn.net/zcpvn/article/details/78150692
                // TODO: 解释2.如果先从左边开始，当出现第一个大于基数的元素时，会将r指向的元素直接覆盖掉
                while (l < r && arr[r] >= temp) r--;
                arr[l] = arr[r];

                while (l < r && arr[l] <= temp) l++;
                arr[r] = arr[l];
            }

            arr[l] = temp;
            quickSort(arr, left, l - 1);
            quickSort(arr, l + 1, right);
        }
    }

    /**
     * 中尉排序有点复杂
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {

        int l = left, r = right, pivot = arr[(left + right) / 2];

        while (l < r) {

            // TODO: 2021/7/6  arr【l】不满足条件时，等于大于pivot，此时都可以与arr[r]交换位置
            //  除非是l》=r，这时候，一定是左右都满足左小右大
            while (arr[l] < pivot) l++;
            while (arr[r] > pivot) r--;

            // TODO: 2021/7/6  如果最后一轮 l++后等于pivot的索引并且r++等于pivot索引
            //  说明此时已经满足pivod左边全部小于它
            //  右边全部大于pivot
            if (l >= r) break;
            // TODO:  如果一边索引先=pivot，那么就是要交换另外一边和pivot位置
            //  如果l和r的索引都未到达pivot所在索引，就是交换两边元素
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[l] == pivot) r--;
            if (arr[r] == pivot) l++;
        }

        // TODO: 因为当l=r时各自向前移动一位，
        //  相当于r所走过的域已经全部大于pivod及中间可能的多个相同值
        //  经过上边这个步骤的--和++，可能造成相等，如果相等的情况下会栈溢出
        if (r == l) {
            r--;
            l++;
        }

        // TODO: 2021/7/6
        if (left < r) {
            quickSort(arr, left, r);
        }
        if (l < right) {
            quickSort(arr, l, right);
        }
    }
}
